#include<iostream>
#include<assert.h>
using namespace std;

enum Colour
{
	READ,
	BLACK
};
template<class T >
struct RBTreeNode
{
	RBTreeNode<T>* _pLeft;
	RBTreeNode<T>* _pRight;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;

	//构造函数
	RBTreeNode(const T data)
		:_pLeft(nullptr)
		, _pRight(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(READ)
	{}
	RBTreeNode()
		:_pLeft(nullptr)
		, _pRight(nullptr)
		, _parent(nullptr)
		, _data(0)
		, _col(BLACK)
	{}
};



template<class T>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T> Self;

	RBTreeIterator(Node* pNode)
		: _pNode(pNode)
	{}

	// 让迭代器具有类似指针的行为
	T& operator*()
	{
		return _pNode->_data;
	}
	T* operator->()
	{
		return &(_pNode->_data);
	}


	// 让迭代器可以移动：前置/后置++  
	//如果右子树不为空，访问右子树最左
	//否则  祖先找孩子是父亲左的孩子
	Self& operator++()
	{
		//右为空，找祖先
		if (_pNode->_pRight == nullptr)
		{
			Node* cur = _pNode;
			Node* parent = cur->_parent;
			while (parent && parent->_pRight == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_pNode = parent;
		}

		//右不为空，找右的最左
		else
		{
			Node* cur = _pNode->_pRight;
			while (cur->_pLeft)
			{

				cur = cur->_pLeft;
			}
			_pNode = cur;

		}
		return *this;

	}
	Self operator++(int)
	{
		Self tmp = *this;
		++(*this);
		return tmp;
	}
	// 然迭代器可以移动：前置/后置-- 
	Self& operator--()
	{
		//左子树为空，往祖父找小
		if (_pNode->_pLeft == nullptr)
		{
			Node* cur = _pNode;
			Node* parent = cur->_parent;
			while (parent && parent->_pLeft)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_pNode = parent;
		}
		//左子树不为空，找小
		else
		{
			Node* cur = _pNode->_pLeft;
			while (cur->_pRight)
			{
				cur = cur->_pRight;
			}
			_pNode = cur;
		}
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	// 让迭代器可以比较
	bool operator!=(const Self& s)const
	{
		return s._pNode != _pNode;
	}
	bool operator==(const Self& s)const
	{
		return s._pNode == _pNode;
	}

private:
	//void Increament();
	//void DeIncreament();
	Node* _pNode;
};


// T: 可能是键值对<key,value>
//    可能是一个key
// 不论节点中存储的是<key, value> || key, 都是按照key来进行比较的
// KeyOfValue: 提取data中的Key
template<class T, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T> iterator;
public:
	RBTree()
	{
		_pHead = new Node;
		_pHead->_pLeft = _pHead;
		_pHead->_pRight = _pHead;
	}

	// 插入值为data的节点
	// 返回值含义：iterator代表新插入节点   bool：代表释放插入成功
	pair<iterator, bool> Insert(const T& data)
	{
		if (_pHead->_pLeft == _pHead)
		{
			_pHead->_data = data;
			_pHead->_pLeft = _pHead->_pRight = nullptr;
			_pHead->_col = BLACK;
			return make_pair(_pHead, true);
		}

		//不为空，查找合适点
		Node* cur = _pHead;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = parent->_pLeft;
			}
			else
				return make_pair(iterator(nullptr), false);
		}

		++_size;
		//找到空位置,链接
		cur = new Node(data);
		Node* newnode = cur;

		if (data < parent->_data) parent->_pLeft = cur;
		else parent->_pRight = cur;
		//双向链接
		cur->_parent = parent;


		//从cur往上检查平衡
		while (parent && parent->_col == READ) //检查连续两个红
		{
			//祖父必定存在
			Node* grandfather = parent->_parent;
			assert(grandfather);
			if (grandfather->_pLeft == parent)
			{
				Node* uncle = grandfather->_pRight;
				//1.叔叔存在且为红
				//父亲叔叔->红  祖父为黑
				if (uncle && uncle->_col == READ)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = READ;

					//祖父会红，可能会导致祖父的父亲出错
					//继续调整
					cur = grandfather;
					parent = grandfather->_parent;
				}
				//2.叔叔存在且为黑 或者叔叔不存在
				//对grandfather 右单旋  p ->黑  g->红
				else
				{
					if (cur == parent->_pLeft)
					{
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = READ;
					}

					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = READ;
					}
					break;
				}
			}


			//grandfather->Right==parent;
			else
			{
				Node* uncle = grandfather->_pLeft;
				if (uncle && uncle->_col == READ)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = READ;

					//继续向上调整
					cur = grandfather;
					parent = cur->_parent;

				}
				//叔叔存在且为黑 --叔叔不存在
				else
				{
					if (cur == parent->_pRight)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = READ;
					}

					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = READ;
					}
					break;
				}
			}
		}
		//暴力调整根
		_pHead->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	// Begin和End迭代器
	iterator begin()
	{
		Node* subLeft = _pHead;
		while (subLeft&&subLeft->_pLeft)
		{
			subLeft = subLeft->_pLeft;
		}
		return iterator(subLeft);
	}
	iterator end()
	{
		return iterator(nullptr);
	}

	// 红黑树是否为红，是返回true，否则返回false
	bool Empty()const
	{
		return _pHead->_pLeft == _pHead;
	}
	// 返回红黑树中有效节点的个数
	size_t Size()const
	{
		return _size;
	}
	// 将红黑树中的有效节点删除，注意：删除的是有效节点，不删除头结点
	void Clear()
	{
		_Destroy(_pHead);
		_size++;
	}
	// 在红黑树中查找data，存在赶回该节点对应的迭代器，否则返回End()
	iterator Find(const T& data)
	{
		Node* cur = _pHead;
		while (cur)
		{
			if (data > cur->_data)
				cur = cur->_pRight;
			else if (data < cur->_data)
				cur = cur->_pLeft;
			else
				return iterator(cur);
		}
		return iterator(nullptr);
	}
	//检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		Node* root = _pHead;
		if (_pHead->_col == READ)
		{
			cout << "根不为黑" << endl;
			return false;
		}
		//任一条作为基准
		size_t BlackCount = 0;
		Node* cur = _pHead;
		while (cur)
		{
			if (cur->_col == BLACK)
				BlackCount++;
			cur = cur->_pLeft;
		}
		size_t k = 0;
		return _IsValidRBTRee(root, k, BlackCount);
	}
private:
	// 为了操作树简单起见：获取根节点
	Node*& GetRoot()
	{
		return _pHead;
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		Node* parentparent = pParent->_parent;

		pParent->_pLeft = subLR;
		if (subLR)
			subLR->_parent = pParent;

		subL->_pRight = pParent;
		pParent->_parent = subL;

		if (pParent == _pHead)
		{
			_pHead = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentparent->_pLeft == pParent)
				parentparent->_pLeft = subL;
			else
				parentparent->_pRight = subL;

			subL->_parent = parentparent;
		}
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		Node* parentparent = pParent->_parent;

		//链接subrl
		pParent->_pRight = subRL;
		if (subRL)
			subRL->_parent = pParent;

		subR->_pLeft = pParent;
		pParent->_parent = subR;

		if (pParent == _pHead)
		{
			_pHead = subR;
			_pHead->_parent = nullptr;
		}
		else
		{
			//判断parentparent的孩子
			if (parentparent->_pLeft == pParent)
				parentparent->_pLeft = subR;

			else
				parentparent->_pRight = subR;

			subR->_parent = parentparent;
		}
	}


	Node* _LeftMost(Node* cur)
	{
		if (cur->_pLeft == nullptr)
			return cur;
		return _LeftMost(cur->_pLeft);
	}

	Node* _RightMost(Node* cur)
	{
		if (cur->_pRight == nullptr)
			return cur;
		return _LeftMost(cur->_pRight);
	}
	void _Destroy(Node*& Root)
	{
		if (Root == nullptr)
		{
			return;
		}
		_Destroy(Root->_pLeft);
		_Destroy(Root->_pRight);
		delete Root;
	}



	bool _IsValidRBTRee(Node* root, size_t k, const size_t& count)
	{
		if (root == nullptr)
		{
			if (count != k)
			{
				cout << "路径和节点黑色数不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == READ && root->_parent->_col == READ)
		{
			cout << "连续红结点" << endl;
			return false;
		}
		if (root->_col == BLACK)
		{
			k++;
		}

		return _IsValidRBTRee(root->_pLeft, k, count) && _IsValidRBTRee(root->_pRight, k, count);
	}


private:
	Node* _pHead;
	size_t _size=1;
};
